package com.jdaw.algorithm.dynamic;

public class KnapsackProblem {
    public static void main(String[] args) {
        int[] w={1,4,3};//物品重量
        int[] value={1500,3000,2000};//物品价值
        int n=value.length;//物品数量
        int m=4;//背包容量
        int[][] v=new int[n+1][m+1];

        //记录放入商品的情况
        int[][] pro=new int[n+1][m+1];
        //初始化第一行第一列为0
        for(int i=0;i<v.length;i++){
            v[i][0]=0;
        }
        for(int i=0;i<v[0].length;i++){
            v[0][i]=0;
        }

        //开始动态规划
        for(int i=1;i<v.length;i++){
            for(int j=1;j<v[0].length;j++){
                if(w[i-1]>j){
                    //因为i从1开始，所以公式的w[i]修改为w[i-1]
                    v[i][j]=v[i-1][j];
                }else{
//                    v[i][j]=Math.max(v[i-1][j], value[i-1]+v[i-1][j-w[i]]);//和上面一样value[i]改为value[i-1]
                    //为了记录商品放入情况抛弃max使用ifelse
                    if(v[i-1][j]<value[i-1]+v[i-1][j-w[i]]){
                        v[i][j]=value[i-1]+v[i-1][j-w[i]];
                        //把当前情况记录到pro中
                        pro[i][j]=1;
                    }else{
                        v[i][j]=v[i-1][j];
                    }
                }
            }
        }

        for (int i=0;i<v.length;i++){
            for(int j=0;j<v[0].length;j++){
                System.out.print(v[i][j]+" ");
            }
            System.out.println("");
        }

    }
}
